﻿using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public interface IListDs<T>   //在定义接口时不能确定函数参数的具体类型，使用泛型接口
{
    int GetLength(); //求长度 
    void Clear(); //清空操作 
    bool IsEmpty(); //判断线性表是否为空 
    void Append(T item); //附加操作 
    void Insert(T item, int location); //插入操作 
    T Delete(int i); //删除操作 
    T GetElem(int i); //取表元 
    int Locate(T value); //按值查找 
}


public class SeqList<T> : IListDs<T>
{
    private int maxSize; //顺序表的最大长度                    (这三个属性通过方法修改，不能直接修改字段)
    private T[] data; //用于存储顺序表中的数据元素
    private int last; //顺序表最后一个元素的位置 没有元素表示为-1


    //索引器
    public T this[int index]
    {
        get { return data[index]; }
        set { data[index] = value; }
    }

    public int MaxSize
    {
        get { return maxSize; }
        set { maxSize = value; }
    }

    public int Last
    {
        get { return last; }
        set { last = value; }
    }

    //构造器
    public SeqList(int size)
    {
        data = new T[size];
        maxSize = size;
        last = -1;
    }

    public int GetLength()
    {
        return last + 1;
    }

    public void Clear()
    {
        //   data = new T[maxSize];  (获取时候通过下标控住，有下标必定重新赋值)
        last = -1;
    }

    public bool IsEmpty()
    {
        if (last == -1)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public bool IsFull()
    {
        if (last + 1 == maxSize)
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    //在表未满的情况下在表尾添加一个元素
    public void Append(T item)
    {
        if (IsFull())
        {
            Debug.Log("List is full!");
        }
        else
        {
            data[++last] = item;
        }
    }

    public void Insert(T item, int location)
    {
        if (IsFull())
        {
            Debug.Log("List is full!");
            return;
        }

        if (location < 1 || location > last + 2)
        {
            Debug.Log("Position is error！");
            return;
        }

        last += 1;

        if (location == last + 2)
        {
            data[last + 1] = item;
        }
        else
        {
            for (int i = last; i >= location - 1; i--) //这里的location -1 特别重要
            {
                data[i + 1] = data[i];
            }

            data[location - 1] = item;
        }
    }

    public T Delete(int location)
    {
        T temp = default(T);

        if (IsEmpty())
        {
            Debug.Log("List is empty");
            return temp;
        }

        if (location < 1 || location > last + 1)
        {
            Debug.Log("Position is error");
            return temp;
        }

        if (location == last + 1)
        {
            temp = data[last--];
        }
        else
        {
            temp = data[location - 1];

            for (int i = location - 1; i <= last; i++) //这里用 <= last 是将last附一个last+1 的空值
            {
                data[i] = data[i + 1];
            }

            last--;
        }
        return temp;
    }

    public T GetElem(int location)
    {
        T temp = default(T);
        if (IsEmpty())
        {
            Debug.Log("List is empty!");
            return temp;
        }

        if (location < 1 || location > last + 1)
        {
            Debug.Log("Position is errror!");
            return temp;
        }

        return data[location - 1];
    }

    public int Locate(T value)
    {
        if (IsEmpty())
        {
            Debug.Log("List is empty!");
            return -1;
        }

        int temp = -1;
        for (int i = 0; i < last; i++)
        {
            if (value.Equals(data[i]))
            {
                temp = i;
                break;
            }
        }

        return temp;
    }

    public void ReversSeqList()
    {
        T temp;
        int len = GetLength();
        Debug.Log(len/2);

        for (int i = 0; i < len/2; i++)
        {
            temp = data[i];
            data[i] =data[len - i -1];
            data[len - i - 1] = temp;
        }
    }
}